package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func Comm_Ancestor(root , p, q *TreeNode) *TreeNode {
	if root == nil{
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val{
		return root
	}
	left := Comm_Ancestor(root.Left, p, q)
	right := Comm_Ancestor(root.Right, p, q)
	//如果left和right都不为空，说明此时root就是最近公共节点
	if left != nil && right != nil{
		return root
	}
	if left == nil{
		return right
	}

	fmt.Println("p,q的公共节点为", left.Val)
	return left
}

func main() {
	root := &TreeNode{Val: 1}
	root.Right = &TreeNode{Val: 3}
	root.Right.Left = &TreeNode{Val: 6}
	root.Right.Left.Left = &TreeNode{Val: 12}
	root.Right.Left.Right = &TreeNode{Val: 13}
	root.Right.Right=&TreeNode{Val: 7}
	root.Right.Right.Right=&TreeNode{Val: 15}
	root.Right.Right.Left=&TreeNode{Val: 14}
	root.Left = &TreeNode{Val: 2}
	root.Left.Left = &TreeNode{Val: 4}
	root.Left.Left.Left = &TreeNode{Val: 8}
	root.Left.Left.Right = &TreeNode{Val: 9}
	root.Left.Right = &TreeNode{Val: 5}
	root.Left.Right.Right = &TreeNode{Val: 11}
	root.Left.Right.Left = &TreeNode{Val: 10}

	fmt.Println(Comm_Ancestor(root, &TreeNode{Val: 9}, &TreeNode{Val: 11})) // 输出 3
}